package 开始的剑指offer8月.链表;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
//https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

public class 面试题06从尾到头打印链表0814 {
     class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
    //普通方法
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[]{};

        // 1. 计算链表的长度
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        // 2. 初始化存放结果的数组
        int[] res = new int[length];

        // 3. 按照反方向将链表节点值存放在数组中
        int i = length - 1;
        curr = head;
        while (curr != null) {
            res[i] = curr.val;
            i--;
            curr = curr.next;
        }

        return res;
    }
//    时间复杂度：O(n)
//    空间复杂度：O(n)

    //辅助栈
    public int[] reversePrint1(ListNode head) {
        if (head == null) return new int[]{};

        // 1. 先将链表从头至尾的节点依次添加到栈中
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }

        // 2. 依次从栈中取出节点，然后添加到数组中
        int[] res = new int[stack.size()];
        int i = 0;
        while (!stack.isEmpty()) {
            res[i] = stack.pop().val;
            i++;
        }

        return res;
    }

    //辅助栈
    public int[] reversePrint2(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null) {
            stack.addLast(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = stack.removeLast();
        return res;
    }
    //递归
    class Solution {
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        public int[] reversePrint(ListNode head) {
            recur(head);
            int[] res = new int[tmp.size()];
            for(int i = 0; i < res.length; i++)
                res[i] = tmp.get(i);
            return res;
        }
        void recur(ListNode head) {
            if(head == null) return;
            recur(head.next);
            tmp.add(head.val);
        }
    }

}
